package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *  题目 ；二叉树每层的最大值
 *  题目详述 ：
 *  给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 */
public class LargestValues {
    /**
     * 核心思想 ：
     *  方法一 ：使用单个队列对于整个二叉树进行遍历，同时通过定义current和next来记录二叉树当前层数的节点数和下一层的节点数
     *
     *  遍历整个二叉树的过程中，获取当前层中下一层的节点数；
     *  current : 表示当前层数剩余节点数；
     *  next : 表示下一层剩余节点数；
     * @param root
     * @return
     */
//    public List<Integer> largestValues(TreeNode root) {
//        // 初始化
//        int currentSum = 0;
//        int nextSum = 0;
//        Queue<TreeNode> queue = new LinkedList<>(); // 队列，存储二叉树节点
//        if(root != null){
//            // 若是根节点不为null的话，即将根节点加入队列中，同时将当前层数节点数+1
//            queue.offer(root);
//            currentSum++;
//        }
//
//        List<Integer> result = new ArrayList<>();
//        int max = Integer.MIN_VALUE;
//        // 需要遍历整个二叉树
//        while (!queue.isEmpty()){
//            // 临时保存队列中删除的节点，用于判断所删除的节点的左右子节点是否为空
//            TreeNode pollNode = queue.poll();
//            currentSum--; // 当前层数剩余节点数减一
//            max = Math.max(max , pollNode.val);
//
//            if (pollNode.left != null){
//                queue.offer(pollNode.left);
//                nextSum++;
//            }
//            if (pollNode.right != null){
//                queue.offer(pollNode.right);
//                nextSum++;
//            }
//            // 当当前层数剩余节点数为零时，结束遍历
//            if(currentSum == 0){
//                result.add(max);
//                max = Integer.MIN_VALUE;
//                currentSum = nextSum;
//                nextSum = 0;
//            }
//        }
//        return result;
//    }
    /**
     *  总结 ：
     *  （1）遍历二叉树（只要满足 ：其为二叉树即可），通过队列来遍历整个二叉树，
     *      遍历方式 ：即，层层遍历，从每层的首元素遍历至每层的尾元素
     *      while循环判断是否队列为空，若是不为空的话，删除队首节点，若是所删除的队首节点存在左右子节点的话，即需要将其加入队列
     *  （2）时间复杂度 ；O（n）
     */

    /**
     *  核心思想 ：
     *  方法二 ：使用双队列来实现二叉树的遍历
     *
     *  即，使用queue1来存储二叉树当前层的节点，同时使用queue2来存储二叉树下一层的节点
     */
    public List<Integer> largestValues(TreeNode root) {
        // 使用queue1来存储二叉树当前层的节点，同时使用queue2来存储二叉树下一层的节点
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();

        // 需要考虑极端情况，若是root根节点为空的话,直接返会空的结果集合即可
        if(root != null){
            queue1.offer(root);
        }

        List<Integer> result = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        while(!queue1.isEmpty()){
            TreeNode pollNode = queue1.poll();
            max = Math.max(max , pollNode.val);

            if (pollNode.left != null){
                queue2.offer(pollNode.left);
            }
            if(pollNode.right != null){
                queue2.offer(pollNode.right);
            }
            if(queue1.isEmpty()){
                result.add(max);
                max = Integer.MIN_VALUE;
                // 使得queue1 = queue2
                // （即，当queue1将二叉树当前层的节点遍历结束后，需要开始遍历二叉树下一次的节点）
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return result;
    }
    /**
     * 总结 ：
     *  （1）即，使用queue1队列来存储二叉树每一层的所有节点，同时queue2队列来存储二叉树下一层的所有节点；
     *  （2）空间复杂度 ：两个队列的空间复杂度（取决于二叉树每一层的树节点数）
     *  （2）时间复杂度 ：O（n），其中 n为二叉树的节点数；
     */
}
